原帖地址：http://blog.leanote.com/post/dawnmagnet/61cf7456274e
# 题目
![title](https://leanote.com/api/file/getImage?fileId=60914f84ab6441786b01a2e
1)
# 思路分析
这道题总的来说值得上困难题。一开始看，一眼就看出是个dp，因为首先房子的数量太
多，如果使用模拟(dfs)必定超时，而我之前说过，但凡是可以用dfs的地方就可以试试d
p。
在这个问题中，给入了三个关键变量，m,n,target，这三个一看就是有大用处的（此处
暗示三维dp），那么为什么使用三维dp而不是大家很好想到的二维dp呢，原因很简单，
我们得在dp的系数上表示出遍历到了哪一个房子，这个房子的颜色可以有几种选择，这
个房子与之前的一起构成了几个街区。这样一来就三个变量了。至于为什么第三个变量
是“这个房子与之前的一起构成了几个街区”，原因很简单，其实dp的每个系数的选择都
是有考虑的，每一个变量都尽可能地和前面已经遍历过的产生逻辑上的联系，这三个变
量的选择都有联系，其中第一个和第三个的联系比较好看出来，而第二个颜色大家可能
会想，并没什么联系，但是大家别忘了颜色对于街区的限制也是一个联系哦！
确定了三个系数的含义，再确定值的含义。因为题目要我们求最小值，那么我们就把值
确定为最小值，这样遍历的时候也方便。
那么来到的最最重要的递推关系式。
## DP的核心-递推关系
先确定最核心的递推逻辑。
```cpp
// dp[i][j][n] m * n * target
// i房子，颜色j，已经有n个街区的最小cost
// 递推：dp[i + 1][jt][k + 1] min= dp[i][j][k] + cost[i + 1][jt] * (house[i + 
1] != 0);
//       dp[i + 1][j][k] min= dp[i][j][k] + cost[i + 1][j] * (house[i + 1] != 
0);
```
PS:这是我在写题的时候打的草稿，一定要打草稿，特别是DP，D到最后你自己都不知道
你在D什么
这两句分别代表两种情况，一共是四种，分别是有无新增区块，是否可以涂颜色（house
是否等于0）
这是最最核心的逻辑，前后两种颜色不一样的时候就会新增区块，house不等于0才需要
加涂装，否则**不能**涂装(不是不想，是不能)
确定了核心逻辑之后，再仔细检查细枝末节。
在确定dp关系的时候，**一定要**精确的领会题目中每一句话的意思。确保每一句话对
应的递推式和它所适用的情况都被推到了出来。
因为是表现最小值，我们在取初始值的时候就先按照INT_MAX(在rust中为i32::MAX)来表
示非法值，也就是无法访问的情况。在处理时我们只处理合法的情况。
注意看题目，**已经被涂过的房子不需要涂色**。所以在判断房子时，先判断有没有颜
色，有颜色就可以直接一步到位，不需要遍历该房颜色了。没有颜色则需要遍历该房颜
色。
为了精简数组的元素，我们将表示街区的长度就设置为target，因为最小的街区数是1，
我们就用0代替（节省空间And剪枝），所以说，当街区数目达到target-1时间到顶了，
我们也不用再向>=target的方向遍历，对于答案来说没有意义。那么又要分好多种情况
，因为有的情况是增加区块的，有的情况是不增加区块的。所以又要检查。（这就是这
道题的困难之处，就是非常复杂）
### Rust代码
```rust
impl Solution {